#include <stdio.h>
#include <assert.h>

#define LEFT  0
#define RIGHT 1
#define CCW   0
#define CW    1

enum cube_stat{
    STAT_DF=0,STAT_DB,  STAT_DL,  STAT_DR,
    STAT_UF,  STAT_UB,  STAT_UL,  STAT_UR,
    STAT_FL,  STAT_FR,  STAT_FU,  STAT_FD,
    STAT_BL,  STAT_BR,  STAT_BU,  STAT_BD,
    STAT_LF,  STAT_LB,  STAT_LU,  STAT_LD,
    STAT_RF,  STAT_RB,  STAT_RU,  STAT_RD,
};

enum cube_flip {
    FLIP_90_LEFT_CW   = 0,
    FLIP_180_LEFT     = 1,
    FLIP_90_LEFT_CCW  = 2,
    FLIP_90_RIGHT_CW  = 3,
    FLIP_180_RIGHT    = 4,
    FLIP_90_RIGHT_CCW = 5,
    FLIP_NULL         = 7,
};
enum cube_twist {
    TWIST_90_LEFT_CW   = 0,
    TWIST_180_LEFT     = 1,
    TWIST_90_LEFT_CCW  = 2,
    TWIST_90_RIGHT_CW  = 3,
    TWIST_180_RIGHT    = 4,
    TWIST_90_RIGHT_CCW = 5,
    TWIST_NULL         = 7,
};
            
// orig|90,LEFT,CW|180,LEFT|90,LEFT,CCW|90,RIGHT,CW|180,RIGHT|90,RIGHT,CCW
// 使用cube_table.py自动生成
const char cube_status_tab[24][6]={
    // 90,LEFT,CW|180,LEFT|90,LEFT,CCW|90,RIGHT,CW|180,RIGHT|90,RIGHT,CCW
    {STAT_DL, STAT_DB, STAT_DR, STAT_RF, STAT_UF, STAT_LF}, // flip from STAT_DF
    {STAT_DR, STAT_DF, STAT_DL, STAT_LB, STAT_UB, STAT_RB}, // flip from STAT_DB
    {STAT_DB, STAT_DR, STAT_DF, STAT_FL, STAT_UL, STAT_BL}, // flip from STAT_DL
    {STAT_DF, STAT_DL, STAT_DB, STAT_BR, STAT_UR, STAT_FR}, // flip from STAT_DR
    {STAT_UR, STAT_UB, STAT_UL, STAT_LF, STAT_DF, STAT_RF}, // flip from STAT_UF
    {STAT_UL, STAT_UF, STAT_UR, STAT_RB, STAT_DB, STAT_LB}, // flip from STAT_UB
    {STAT_UF, STAT_UR, STAT_UB, STAT_BL, STAT_DL, STAT_FL}, // flip from STAT_UL
    {STAT_UB, STAT_UL, STAT_UF, STAT_FR, STAT_DR, STAT_BR}, // flip from STAT_UR
    {STAT_FD, STAT_FR, STAT_FU, STAT_UL, STAT_BL, STAT_DL}, // flip from STAT_FL
    {STAT_FU, STAT_FL, STAT_FD, STAT_DR, STAT_BR, STAT_UR}, // flip from STAT_FR
    {STAT_FL, STAT_FD, STAT_FR, STAT_RU, STAT_BU, STAT_LU}, // flip from STAT_FU
    {STAT_FR, STAT_FU, STAT_FL, STAT_LD, STAT_BD, STAT_RD}, // flip from STAT_FD
    {STAT_BU, STAT_BR, STAT_BD, STAT_DL, STAT_FL, STAT_UL}, // flip from STAT_BL
    {STAT_BD, STAT_BL, STAT_BU, STAT_UR, STAT_FR, STAT_DR}, // flip from STAT_BR
    {STAT_BR, STAT_BD, STAT_BL, STAT_LU, STAT_FU, STAT_RU}, // flip from STAT_BU
    {STAT_BL, STAT_BU, STAT_BR, STAT_RD, STAT_FD, STAT_LD}, // flip from STAT_BD
    {STAT_LU, STAT_LB, STAT_LD, STAT_DF, STAT_RF, STAT_UF}, // flip from STAT_LF
    {STAT_LD, STAT_LF, STAT_LU, STAT_UB, STAT_RB, STAT_DB}, // flip from STAT_LB
    {STAT_LB, STAT_LD, STAT_LF, STAT_FU, STAT_RU, STAT_BU}, // flip from STAT_LU
    {STAT_LF, STAT_LU, STAT_LB, STAT_BD, STAT_RD, STAT_FD}, // flip from STAT_LD
    {STAT_RD, STAT_RB, STAT_RU, STAT_UF, STAT_LF, STAT_DF}, // flip from STAT_RF
    {STAT_RU, STAT_RF, STAT_RD, STAT_DB, STAT_LB, STAT_UB}, // flip from STAT_RB
    {STAT_RF, STAT_RD, STAT_RB, STAT_BU, STAT_LU, STAT_FU}, // flip from STAT_RU
    {STAT_RB, STAT_RU, STAT_RF, STAT_FD, STAT_LD, STAT_BD}, // flip from STAT_RD
};

// a: 需要进行的操作，取值范围如下
// "U", "R", "F", "D", "L", "B"
// "U'", "R'", "F'", "D'", "L'", "B'"
// "U2", "R2", "F2", "D2", "L2", "B2"
// stat: 魔方的朝向，取值范围如下(0-23)
//    STAT_DF,STAT_DB, STAT_DL, STAT_DR,
//    STAT_UF, STAT_UB, STAT_UL, STAT_UR,
//    STAT_FL, STAT_FR, STAT_FU, STAT_FD,
//    STAT_BL, STAT_BR, STAT_BU, STAT_BD,
//    STAT_LF, STAT_LB, STAT_LU, STAT_LD,
//    STAT_RF, STAT_RB, STAT_RU, STAT_RD,
// last_lr: 最后移动过的机械臂，下次操作时，会尽量选择同侧的
// LEFT  0
// RIGHT 1

// 返回值：魔方的朝向，取值范围和stat一样
static int cube_tweak(int stat, const char *a, int *last_lr, char *flip_twist)
{
    int lr = LEFT;
    int flip = FLIP_NULL;
    int twist = TWIST_NULL;
    const char cube_face_code[6] = {'U', 'R', 'F', 'D', 'L', 'B'};
    const char cube_stat_decode[24] = {
        0x32,0x35,0x34,0x31,
        0x02,0x05,0x04,0x01,
        0x24,0x21,0x20,0x23,
        0x54,0x51,0x50,0x53,
        0x42,0x45,0x40,0x43,
        0x12,0x15,0x10,0x13,
    }; 
    for(int face = 0; face < 6; face ++)
    {
        if(cube_face_code[face] == a[0])
        {
            // 将取值范围0-23的stat转为cube_stat_decode中描述的形式，方便判断可操作的面
            char stat_decode = cube_stat_decode[stat];
            printf("action == %c%c, status == %c%c\n", a[0], a[1], cube_face_code[stat_decode>>4], cube_face_code[stat_decode&0x0f]);
            if((stat_decode & 0xF0) == (face << 4))
            {
                // 拧左边
                lr = LEFT;
            }
            else if((stat_decode & 0x0F) == face)
            {
                // 拧右边
                lr = RIGHT;
            }
            else
            {
                // 需要调整魔方方向
                int start, end, add, i;
                // last_lr: 最后移动过的机械臂，翻转魔方操作时，尽量选择同侧的机械臂
                // 和上次动作同为90度时，可以节省一些操作步骤
                if(*last_lr == LEFT)
                {
                    start = 0;
                    end = 6;
                    add = 1;
                }
                else
                {
                    start = 5;
                    end = -1;
                    add = -1;
                }
                for(i=start; i != end; i+=add)
                {
                    int next = cube_status_tab[stat][i];
                    char next_stat_decode = cube_stat_decode[next];
                    if((next_stat_decode & 0xF0) == (face << 4))
                    {
                        lr = LEFT;
                        flip = i;
                        stat = next;
                        break;
                    }
                    else if((next_stat_decode & 0x0F) == face)
                    {
                        lr = RIGHT;
                        flip = i;
                        stat = next;
                        break;
                    }
                }
            }
            break;
        }
    }
    *last_lr = lr;
    // 拧魔方
    if('\'' == a[1])
    {
        if(LEFT == lr){
            twist = TWIST_90_LEFT_CCW;
        }else{
            twist = TWIST_90_RIGHT_CCW;
        }
    }
    else if('2' == a[1])
    {
        if(LEFT == lr){
            twist = TWIST_180_LEFT;
        }else{
            twist = TWIST_180_RIGHT;
        }
    }
    else
    {
        if(LEFT == lr){
            twist = TWIST_90_LEFT_CW;
        }else{
            twist = TWIST_90_RIGHT_CW;
        }
    }
    flip_twist[0] = (char)flip;
    flip_twist[1] = (char)twist;
    return stat;
};

// 按照求解结果执行动作
static int cube_tweak_str(int stat, const char *str)
{
    const int MAX_STEP = 25;
    const char *p = str;
    int count = 0;// 步骤数量
    int last_lr = LEFT; // 最后移动过的机械臂，下次操作时，会尽量选择同侧的
    char motion_table[MAX_STEP][2];// {flip, twist}
    while(1)
    {
        if(*p == 'U' || *p == 'R' || *p == 'F' || *p == 'D' || *p == 'L' || *p == 'B'){
            stat = cube_tweak(stat, p, &last_lr, motion_table[count]);
            p++;
            count++;
            if(*p == 0 || count >= MAX_STEP){
                break;
            }
        }
        p++;
        if(*p == 0){
            break;
        }
    }
    //printf("count=%d\n", count);
    for(int i=0; i<count-1; i++)
    {
        int twist = motion_table[i][1];
        int flip = motion_table[i+1][0];
        if((flip == FLIP_90_LEFT_CW || flip == FLIP_90_LEFT_CCW) && 
           (twist == TWIST_90_LEFT_CW || twist == TWIST_90_LEFT_CCW))
        {
            motion_table[i][1] |= 0x10;
            motion_table[i+1][0] |= 0x10;
        }
        if((flip == FLIP_90_RIGHT_CW || flip == FLIP_90_RIGHT_CCW) && 
           (twist == TWIST_90_RIGHT_CW || twist == TWIST_90_RIGHT_CCW))
        {
            motion_table[i][1] |= 0x10;
            motion_table[i+1][0] |= 0x10;
        }
    }
    for(int i=0; i<count; i++)
    {
        printf("count = %d\n", i);
        // 翻转魔方动作的编号，例如FLIP_90_LEFT_CW
        int flip = motion_table[i][0] & 0x0F;
        // 拧魔方动作的编号，例如TWIST_90_LEFT_CW
        int twist = motion_table[i][1] & 0x0F;
        // 如果可以跳过手指张开，机械臂旋转90度回零的动作，取值16
        // 如果不能，取值0
        int flip_skip_back_step = motion_table[i][0] & 0x10;
        int twist_skip_back_step = motion_table[i][1] & 0x10;
        switch(flip)
        {
            case FLIP_90_LEFT_CW:
                printf("flip_cube_90(LEFT, CW); %d\n",flip_skip_back_step);
                break;
            case FLIP_180_LEFT:
                printf("flip_cube_180(LEFT);\n");
                break;
            case FLIP_90_LEFT_CCW:
                printf("flip_cube_90(LEFT, CCW); %d\n",flip_skip_back_step);
                break;
            case FLIP_90_RIGHT_CW:
                printf("flip_cube_90(RIGHT, CW); %d\n",flip_skip_back_step);
                break;
            case FLIP_180_RIGHT:
                printf("flip_cube_180(RIGHT);\n");
                break;
            case FLIP_90_RIGHT_CCW:
                printf("flip_cube_90(RIGHT, CCW); %d\n",flip_skip_back_step);
                break;
            default: // FLIP_NULL
                break;
        }
        switch(twist)
        {
            case TWIST_90_LEFT_CW:
                printf("twist_cube_90(LEFT, CW); %d\n",twist_skip_back_step);
                break;
            case TWIST_180_LEFT:
                printf("twist_cube_180(LEFT);\n");
                break;
            case TWIST_90_LEFT_CCW:
                printf("twist_cube_90(LEFT, CCW); %d\n",twist_skip_back_step);
                break;
            case TWIST_90_RIGHT_CW:
                printf("twist_cube_90(RIGHT, CW); %d\n",twist_skip_back_step);
                break;
            case TWIST_180_RIGHT:
                printf("twist_cube_180(RIGHT);\n");
                break;
            case TWIST_90_RIGHT_CCW:
                printf("twist_cube_90(RIGHT, CCW); %d\n",twist_skip_back_step);
                break;
            default: // TWIST_NULL
                break;
        }
    }
    return stat;
}


int main(void)
{
    char scramble_string[]="D R2 U2 L2 B2 D F2 D L2 B2 D L2 F' U B R F2 U L D2 R2 ";
    cube_tweak_str(STAT_DF, scramble_string);
}
/*
   "D R2 U2 L2 B2 D F2 D L2 B2 D L2 F' U B R F2 U L D2 R2 ",
    "B2 F2 D L2 D B2 U' R2 B2 L2 U2 L B' L2 R2 U' R2 U2 R2 B' R ",
    "D2 B' R2 D2 B' U2 B' D2 B2 R2 B U' F' L2 F2 R D' B U' R B' ",
    "B2 D2 F2 D' B2 U B2 U R2 D' L2 U' R D F2 U2 R' F' R F2 R' ",
    "F2 U2 L' B2 U2 F2 L2 F2 U2 R D' B' U' L' F' D F2 D B D' ",
    "R' F2 L2 D2 U2 B2 L U2 L2 R' U' F' L2 B D2 R D2 R2 U F R2 ",
    "D L2 F2 L2 D F2 U' R2 U2 B2 F2 R' F' L' B' U B2 D' B D2 U' ",
    "D2 R2 B2 D2 B' F' R2 D2 B L2 D' L' B D F D B2 R' B U2 R' ",
    "D2 L2 F2 R2 U' R2 D2 F2 D' U2 R2 B L2 F L F R D2 U' B L ",
    "R2 D2 F' L2 R2 B' F' R2 B L' B2 D' B R' F' D B' F2 L2 D2 F' ",
    "D U2 F2 L2 B2 L2 D2 F2 U2 L F U L B2 D2 L' B' L2 D' R D ",
    "R' U2 L D2 R2 D2 F2 R' B2 R D2 U' L' D' B2 L R' B D U' F' ",
    "R2 F' R2 U2 F2 D2 R2 B D2 L2 D2 R2 D' B2 R F' D2 B2 D2 F' D2 ",
    "R2 U2 F' U2 L2 B' F' U2 F R2 F2 L' D L B' R' D' F L2 D2 U2 ",
    "D2 B D2 L2 D2 R2 U2 F' D2 F' L F U' B F L B2 L' U R2 U ",
    "R2 B2 F2 R D2 F2 D2 L U2 L B' F U L2 F D2 L' D' R' F2 U' ",
    "F2 D U2 B2 R2 U R2 D' U2 L2 U2 L D B' U2 R' D2 R2 D2 B D ",
    "L2 B2 L F2 U2 B2 F2 R2 D2 L B2 F' U' L2 D2 B' R2 U2 F D L' ",
    "D F2 U' F2 R2 U F2 R2 D2 B2 F2 L' B' R' U F' U2 L F R' F ",
    "L D2 L' U2 F2 D2 B2 R B2 L' B2 L2 D B L U2 F' U R2 F' D ",
    "U2 L2 R2 F D2 B' F2 D2 R2 B2 U' B2 F' L' D F' L2 R' U' F' ",
    "R2 U' R2 U F2 D' R2 D' R2 D2 F R B2 R2 B2 U B L2 F D2 U2 ",
    "L' F2 U2 L2 F2 L' B2 D2 R' U2 F R B2 D R U' L U B2 L2 U2 ",
    "R2 U2 B F2 D2 L2 F2 L2 F2 U2 L' F2 D F' L B' R F L' F L2 ",
    "D2 U R2 U' F2 L2 F2 U' F2 R' F2 D B2 R' B2 D B R' U B2 U2 ",
    "D B2 U2 L2 B2 D B2 L2 B2 L2 D' L2 F' R' B U' F' R D B2 D2 ",
    "L2 R D2 U2 B2 U2 R' D2 L' R' D' B F' D L U B D2 F R2 D2 ",
    "B2 D2 U2 L' F2 L R2 F2 R2 D2 U R2 B L' U2 F2 R D' U' R2 B' ",
    "U2 F2 D' B2 F2 D B2 U R2 U' B' L2 R F2 R D2 U2 F2 U' L U2 ",
    "L R2 B2 U2 L U2 F2 U2 B2 F2 R2 D' F D B2 R' U B2 F2 U R' ",
*/
